package com.cwj.algorithm.graph;

import java.util.Deque;

/**
 * @author chenwujie
 * @date 2020-12-23 15:03
 * 又香环检测
 */
public class DirectedCycle {
    /**
     * 有向环
     */
    private Digraph digraph;
    /**
     * 标识顶点已作为入口进行检索过
     */
    private boolean[] marked;
    /**
     * 标识从入口顶点到深度优先搜索中已搜索的顶点
     */
    private boolean[] inSearching;
    /**
     * 是否有环
     */
    private boolean cricoid;

    public DirectedCycle(Digraph digraph){
        this.digraph = digraph;
        this.marked = new boolean[digraph.getV()];
        this.inSearching = new boolean[digraph.getV()];
    }

    /**
     * 从各顶点检测是否有环
     */
    public void checkCycle(){
        for (int i = 0; i < digraph.getV(); i++) {
            if(!marked[i]){
                dfs(i);
            }
        }
    }

    private void dfs(int v){
        marked[v] = true;

        inSearching[v] = true;
        Deque<Integer> vertexes = digraph.getVertexes(v);
        for (Integer w : vertexes) {
            if(!marked[w]){
                dfs(w);
            }

            if(inSearching[w]){
                cricoid = true;
                return;
            }
        }
        inSearching[v] = false;
    }

    /**
     * 是否有环
     */
    public boolean isCricoid(){
        return cricoid;
    }
}
